1. Field of the Invention
The invention concerns packet switching generally and packet switching in very high-speed networks in particular.
2. Description of the Prior Art
Increasingly, devices communicate with each other by sending packets of digital data. As shown in FIG. 1, a packet (P 113) is a sequence of bits which one device sends another. Packets generally have two parts: a message (MSG 115), which is the sequence of bits which make up the actual message which is being sent, and a header (HDR 117), which contains control information which the communications system over which the packet is sent uses in transferring the message. At a minimum, header 117 will contain destination (D 119), a value which indicates the destination to which the message is directed. Header 117 may also contain information such as the length of message 115, the type of message 115, or the source of message 115. The manner in which destination 119 indicates the destination will depend on the kind of communications system over which the message is sent. For example, destination 119 may specify the address of the device which is to receive the packet in the network or it may specify a virtual circuit which is currently connecting the source of the packet with its destination.
One way of sending packets between devices is by means of a switched network. A switched network is made up of nodes connected by incoming and outgoing links. A packet switch at each node of the network receives packets on its incoming links, determines from destination 119 where each packet is going, and switches the packet to the outgoing link which will take it to its destination.
FIG. 1 shows a prior-art packet switch 101. Packet switch 101 receives packets from a number of input links at input ports (IP) 107(0 . . . n), switches the packets in switch fabric (SF) 103, and outputs them to output links at output ports (OP) 109(0 . . . n). In most common kinds of prior-art packet switches, switching fabric 103 includes memory 105. Memory 105 contains at a minimum an output queue (OQ) 111 for each output port 109. Switch fabric 103 does the switching by placing each packet received on an input port 107 onto the tail of output queue 111 for output port 109 for the output link which will take the packet to its destination. As switch fabric 103 adds incoming packets 113 to the tails of the output queues, it takes outgoing packets 113 from the heads of the output queues 111 and provides them to output ports 109 corresponding to the queues 111.
A problem with packet switches in modern networks is the switch is often unable to keep up with the speed at which the links can operate. For example, a glass fiber link can operate at speeds of 1 Gigabyte/second. If the switch cannot keep up with that speed, that is, unless the switch can handle simultaneous inputs from a number of links operating at that speed, the network will not be able to use the full capacity offered by the links, but will instead be limited by the rate at which the switches can transfer packets from one link to another. A survey of architectures for fast packet switches may be found in Fouad A. Tobagi, "Fast Packet Switch Architectures for Broad-band Integrated Services Digital Networks", Proceedings of the IEEE, vol. 78, No. 1, January, 1990.
A particularly troublesome area in designing packet switches of the type of packet switch 101 is the limitations that memory 105 places on operating speed. Modern packet switches are of course made up of integrated circuits; in particular, memory 105 is made up of a number of off-the-shelf dynamic RAM integrated circuits. Memory 105 must be both large and fast; however, off-the-shelf dynamic RAM integrated circuits are either large and slow or small and fast. For example, current CMOS memories of 256 Kbits have a cycle time of 35 ns, while those of 4 Mbits have a cycle time of 200 ns. Worse, the product of memory size with cycle time has remained remarkably constant over generations of memory technologies.
If switch 101 is to operate at the necessary speed, enough fast memory integrated circuits must be provided so that memory 105 is wide enough to store an entire packet in a single row of the memory, so that the entire packet can be written to or read from memory 105 in a single operation. Further, the packet must be carried to and from the memory by a bus which is as wide as the memory. However, as a bus becomes wider, it also becomes slower. The large number of parallel lines increases distortion and skew in the data signals, and the bus cycle time must be increased to counteract these effects. Further, crosstalk between the many data lines increases the noise level, so that larger bus drivers and more sensitive receivers are required. As a result of all of these factors, the speed advantages gained by a wide memory 105 are limited by the slowness of the bus which connects the memory integrated circuits making up memory 105 to the remaining integrated circuits making up switch fabric 103 and switch 101 cannot provide provide the gigabytes/second transfer rate which is needed.
It is an object of the high-speed packet switch disclosed in this patent application to overcome the foregoing problems and limitations of prior-art packet switches.